"""
题目：https://leetcode-cn.com/problems/symmetric-tree/
    给定一个二叉树，检查它是否是镜像对称的。
    例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
        1
    / \
    2   2
    / \ / \
    3  4 4  3
    但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
        1
    / \
    2   2
    \   \
    3    3
思路：迭代的方法。先创建一个列表q，保存两棵树的成对称位置的节点，然后每次取出成对称位置的两个结点left和right，判断其是否同时存在以及二者的值是否相等，不相等的话说明这棵树不是对称二叉树，
    相等的话我们需要继续做下去，将left.left和right.right成对放进q中，再将left.right和right.left放进q中，继续进行二叉树是否对称的判断。
    （注意：如果left和right同时为叶结点的话，我们需要继续循环判断下去）
时间复杂度：O(n)
空间复杂度：O(n)
"""
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def check(r1,r2):
            if not r1 or not r2:
                return False
            q = []
            q.append(r1)
            q.append(r2)
            while q:
                left = q.pop()
                right = q.pop()
                if not left and not right:
                    continue
                if not left or not right or left.val != right.val:
                    return False
                q.append(left.left)
                q.append(right.right)
                q.append(left.right)
                q.append(right.left)
            return True
        return check(root,root)